//
// Created by wdq on 2022/9/10.
//
#include <iostream>
#include <vector>
#include <cmath>

template<typename ElemType>
struct ListNode {
    ElemType value;
    ListNode *next;

    /*!
     * 递归释放空间
     */

    void print() {
        std::cout << value << std::endl;
    }


    ListNode() : value(), next(nullptr) {}


    explicit ListNode(ElemType value) : value(value), next(nullptr) {}

    ListNode(ElemType value, ListNode *next) : value(value), next(next) {}

    ~ListNode() {
        delete next;
    }
};

template<typename ElemType>
struct LinkList {
    ListNode<ElemType> *header;
    int length;

    LinkList() {
        this->header = new ListNode<ElemType>();
        this->length = 0;
    }

    ~LinkList() {
        delete header;
    }

    void insertByHead(ElemType value) {
        ListNode<ElemType> *p = header->next;
        header->next = new ListNode<ElemType>(value, p);
        length++;

    }

    void insertByTail(ElemType value) {
        auto p = header;
        for (; p->next != nullptr; p = p->next);
        p->next = new ListNode<ElemType>(value);
        this->length++;

    }

    ListNode<ElemType> *get(int index) {
        if (index < 0 && index >= this->length) {
            throw std::out_of_range("the index is not legal");
        }
        auto p = header->next;
        for (; p != nullptr && index > 0; p = p->next, index--);
        return p;
    }

    void set(int index, ElemType value) {
        auto p = get(index);
        p->value = value;
    }

    ListNode<ElemType> *find(ElemType value) {
        auto p = header->next;
        for (; p != nullptr; p = p->next) {
            if (p->value == value) {
                break;
            }
        }
        return p;

    }

    void deleteAfter(ListNode<ElemType> *p) {
        if (p == nullptr) {
            return;
        }
        auto q = p->next;
        if (q == nullptr) {
            return;
        }
        p->next = q->next;
        q->next = nullptr;
        delete q;
        this->length--;
    }

    void print() {
        std::cout << "header -> ";
        for (auto p = header->next; p != nullptr; p = p->next) {
            std::cout << p->value << " -> ";
        }
        std::cout << "^" << std::endl;
    }
};

template<typename ElemType>
struct Queue : public LinkList<ElemType> {
    ListNode<ElemType> *tail;

    Queue() : LinkList<ElemType>() {
        this->tail = this->header;
    }

    void enqueue(ElemType value) {
        tail->next = new ListNode<ElemType>(value);
        tail = tail->next;
        this->length++;

    }

    ElemType dequeue() {
        if (isEmpty()) {
            throw std::out_of_range("the queue is empty!");
        }
        auto item = this->header->next->value;
        if (this->length == 1) {
            this->tail = this->header;
        }
        LinkList<ElemType>::deleteAfter(this->header);
        return item;

    }

    bool isEmpty() {
        return this->header->next == nullptr;
    }
};


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

    ~TreeNode() {
        delete left;
        delete right;
    }


    static TreeNode *create(std::vector<std::string> nums, int &index) {
        if (index == nums.size()) {
            return nullptr;
        }
        std::string temp = nums[index++];
        if (temp == "null") {
            return nullptr;
        }
        TreeNode *left = create(nums, index);
        TreeNode *right = create(nums, index);
        return new TreeNode(std::stoi(temp), left, right);


    }

    void preOrder() const {
        if (left != nullptr) {
            left->preOrder();
        }
        std::cout << val << " ";
        if (right != nullptr) {
            right->preOrder();
        }
    }

    void inOrder() const {
        std::cout << val << " ";
        if (left != nullptr) {
            left->inOrder();
        }
        if (right != nullptr) {
            right->inOrder();
        }
    }

    void postOrder() const {
        if (left != nullptr) {
            left->postOrder();
        }
        if (right != nullptr) {
            right->postOrder();
        }
        std::cout << val << " ";
    }

    void levelOrder() const {
        Queue<TreeNode *> queue;
        std::cout << val << " ";
        if (left != nullptr) {
            queue.enqueue(left);
        }
        if (right != nullptr) {
            queue.enqueue(right);
        }
        int length = queue.length;
        while (!queue.isEmpty()) {
            while (length != 0) {
                TreeNode *node = queue.dequeue();
                std::cout << node->val << " ";
                if (node->left != nullptr) {
                    queue.enqueue(node->left);
                }
                if (node->right != nullptr) {
                    queue.enqueue(node->right);
                }
                length--;
            }
            length = queue.length;

        }
    }


};

int getDepth(TreeNode *root) {
    if (root == nullptr) {
        return 0;
    }
    return std::max(getDepth(root->left), getDepth(root->right)) + 1;
}

void orderTree(TreeNode *root, int x, int y, std::vector<std::vector<std::string>> &res) {
    if (root == nullptr) {
        return;
    }
    res[x][y] = std::to_string(root->val);
    int temp = int(pow(2, int(res.size()) - 1 - x - 1));
    orderTree(root->left, x + 1, y - temp, res);
    orderTree(root->right, x + 1, y + temp, res);
}

void printTree(TreeNode *root) {
    auto depth = getDepth(root);
    std::vector<std::vector<std::string> > res(depth, std::vector<std::string>(int(pow(2, depth) - 1)));
    orderTree(root, 0, (int(res[0].size()) - 1) / 2, res);
    for (auto &i: res) {
        for (auto &j: i) {
            if (j.empty()) {
                std::cout << " ";
            } else {
                std::cout << j;
            }
        }
        std::cout << std::endl;
    }

}


int main() {
    int index = 0;
    std::vector<std::string> nums = {"3", "0", "null", "2", "1", "null", "null", "null", "4"};
    std::cout << "the tree:" << std::endl;
    TreeNode *treeNode = TreeNode::create(nums, index);
    printTree(treeNode);

    std::cout << "preOrder: ";
    treeNode->preOrder();
    std::cout << std::endl;

    std::cout << "inOrder: ";
    treeNode->inOrder();
    std::cout << std::endl;

    std::cout << "postOrder: ";
    treeNode->postOrder();
    std::cout << std::endl;

    std::cout << "levelOrder: ";
    treeNode->levelOrder();
    std::cout << std::endl;

    delete treeNode;
    return 0;
}